package 中等.动态规划.其他;

/**
 * 沿街有一排连续的房屋。每间房屋内都藏有一定的现金。现在有一位小偷计划从这些房屋中窃取现金。
 * 由于相邻的房屋装有相互连通的防盗系统，所以小偷 不会窃取相邻的房屋 。
 * 小偷的 窃取能力 定义为他在窃取过程中能从单间房屋中窃取的 最大金额 。
 * 给你一个整数数组 nums 表示每间房屋存放的现金金额。形式上，从左起第 i 间房屋中放有 nums[i] 美元。
 * 另给你一个整数 k ，表示窃贼将会窃取的 最少 房屋数。小偷总能窃取至少 k 间房屋。
 * 返回小偷的 最小 窃取能力。
 */
public class 打家劫舍IV_2560 {

    public static void main(String[] args) {

        System.out.println(getMaxK(new int[]{2, 7, 9, 3, 1}, 1));

    }

    /**
     * 二分+动态规划
     * 1，二分枚举窃取能力，窃取能力越大可以窃取的最大房屋就越多
     * 2，使用动态规划计算，当窃取能力为 capacity 时，可以窃取的
     * 最大房屋数量
     */
    public static int minCapability(int[] nums, int k) {
        int capacity = Integer.MAX_VALUE;
        int left = 0, right = 1_000_000_000;

        while (left <= right) {
            int mid = left + (right - left) / 2;
            int curMaxK = getMaxK(nums, mid);
            if (curMaxK >= k) {
                capacity = Math.min(capacity, mid);
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }

        return capacity;
    }

    private static int getMaxK(int[] nums, int capacity) {
        int[] dp = new int[nums.length];

        for (int i = 0; i < dp.length; i++) {
            // 窃取能力不足
            if (nums[i] > capacity) {
                if (i - 1 >= 0)
                    dp[i] = dp[i - 1];
                continue;
            }
            dp[i] = Math.max((i - 2 < 0 ? 0 : dp[i - 2]) + 1, i - 1 < 0 ? 0 : dp[i - 1]);
        }
        return dp[dp.length - 1];
    }

}
